package com.zk.algorithm.others;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCode;

import java.util.Stack;

/**
 * 最长有效括号对
 *
 * https://leetcode.com/problems/longest-valid-parentheses/solution/
 */
@Hard
@LeetCode("32")
public class LongestValidParentheses {

    /**
     * 栈的解法
     *
     * - 当计算最大长度的时候，栈顶指针指向的永远都是左括号减 1 的位置
     * - 以 "()" 为例，当 i 走向 ")" 的时候，即 i = 1，栈里面是 -1, 0。所以先 pop 一下，表示左括号 pop 出去，所以 1 - -1 = 2 恰好是距离
     * - 以 "()(())" 为例，当 i 走向 4 的时候，栈：[-1, 2, 3]，把 3 pop 出去，4 - 2 = 2
     * - 以 "()(())" 为例，当 i 走向 5 的时候，栈：[-1, 2]，把 2 pop 出去，5 - -1 = 6
     *
     * @param s
     * @return
     */
    public int longestValidParenthesesWithStackSolution(String s) {
        int maxans = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        // ()(()))))
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                }

                if (stack.empty()) {
                    // ==================
                    // 一旦为空，表示阶段性结束，表示前面的字符串一定不是有效字符串
                    // 没有连接起来，即 "有效括号对 i 有效括号对"，前后两个有效括号对是独立的
                    //
                    // -1
                    // ↓
                    // 无 ( ) ) ( ) ( )
                    //       ↑
                    //       i
                    // ==================
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }

        return maxans;
    }

    /**
     * Input: ")()())"
     * Output: 4
     * Explanation: The longest valid parentheses substring is "()()"
     *
     * 动态规划算法 - 太难了 - 没有弄懂
     *
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        if (s.length() <= 1)
            return 0;

        int curMax = 0;
        // ======================
        // longest[i] 以 i 结束的字符串的最长有效括号对的长度
        // ======================
        int[] longest = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // =========================
                    //                 ↓
                    // x x x x x x x ( )
                    //               ↑
                    // =========================
                    longest[i] = (i - 2) >= 0 ? (longest[i - 2] + 2) : 2;
                    curMax = Math.max(longest[i], curMax);
                } else { // if s[i-1] == ')', combine the previous length.
                    if (i - longest[i - 1] - 1 >= 0 && s.charAt(i - longest[i - 1] - 1) == '(') {
                        longest[i] = longest[i - 1] + 2 + ((i - longest[i - 1] - 2 >= 0) ? longest[i - longest[i - 1] - 2] : 0);
                        curMax = Math.max(longest[i], curMax);
                    }
                }
            } else if (s.charAt(i) == '(') {
                // ======================
                // 直接将 longest[i] 置位 0
                // 因为任何以 '(' 结束的字符串都是非法括号对
                // ======================
                // skip it, because longest[i] must be 0
            }
        }

        return curMax;
    }

    public static void main(String...args) {
        LongestValidParentheses longestValidParentheses = new LongestValidParentheses();

//        Utils.println(longestValidParentheses.longestValidParenthesesWithStackSolution("(()()"));
        Utils.println(longestValidParentheses.longestValidParenthesesWithStackSolution("()(()))))"));
    }

}
